package com.c2b.algorithm.leetcode.base;

import java.util.TreeSet;

/**
 * 第三大的数
 * <p>给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。</p>
 *
 * @author c2b
 * @since 2022/5/19 15:47
 */
public class LC0414 {

    /**
     * 获取数组中第三大的数 。如果不存在，则返回数组中最大的数。
     *
     * @param nums 数组
     * @return int 第三大的数
     * @author c2b
     * @since 2022/5/19 15:51
     */
    public int thirdMax(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int num : nums) {
            set.add(num);
            if (set.size() > 3) {
                set.remove(set.first());
            }
        }
        return set.size() == 3 ? set.first() : set.last();
    }

    public int thirdMax2(int[] nums) {
        // 最大的数
        Integer maxNum = null;
        // 第二大的数
        Integer secondNum = null;
        // 第三大的数
        Integer thirdNum = null;
        for (int num : nums) {
            if (maxNum == null || num > maxNum) {
                thirdNum = secondNum;
                secondNum = maxNum;
                maxNum = num;
            } else if (maxNum > num && (secondNum == null || num > secondNum)) {
                thirdNum = secondNum;
                secondNum = num;
            } else if (secondNum != null && secondNum > num && (thirdNum == null || num > thirdNum)) {
                thirdNum = num;
            }
        }
        return thirdNum == null ? maxNum.intValue() : thirdNum.intValue();
    }

    public static void main(String[] args) {
        int[] ints = {3, 2, 1};
        System.out.println(new LC0414().thirdMax2(ints));
    }
}
